package com.hjx.other;

/**
 * 在排序数组中查找数字
 *
 * 数字在排序数组中出现的次数
 *
 * 统计一个数字在排序数组中出现的次数， 例如
 * [1,2,3,3,3,3,4,5]
 * 3出现了4次 因此输出4
 *
 */
public class FindXDupCount {

    /**
     * 改进版 二分法找第一个和找最后一个，然后两元素索引做差+1
     */
    public int findFirstX(int[] arr, int x, int lo, int hi) {
        if (lo > hi) {
            return -1;
        }

        int mid = (hi + lo) / 2;

        if(arr[mid] > x) {
            hi = mid - 1;
        } else if(arr[mid] < x) {
            lo = mid + 1;
        } else {

            if ((mid > 0 && arr[mid-1] != x) || mid == 0){
                return mid;
            } else {
                hi = mid - 1;
            }
        }
        return findFirstX(arr, x, lo, hi);
    }

    public int findLastX(int[] arr, int x, int lo, int hi) {
        if (lo > hi) {
            return -1;
        }

        int mid = (hi + lo) / 2;

        if(arr[mid] > x) {
            hi = mid - 1;
        } else if(arr[mid] < x) {
            lo = mid + 1;
        } else {
            if ((mid < arr.length - 1 && arr[mid+1] != x) || mid == arr.length - 1){
                return mid;
            } else {
                lo = mid + 1;
            }

        }

        return findLastX(arr, x, lo, hi);
    }


    /**
     * 二分法 + 左右扫描 时间复杂度O（n）
     *
     * @param arr
     * @param x
     * @return
     */
    public int findXDupCount(int[] arr, int x, int lo, int hi) {
        if (lo > hi) {
            return -1;
        }
//        int hi = arr.length - 1;
//        int lo = 0;

        int mid = (hi + lo) / 2;

        if(arr[mid] > x) {
            hi = mid - 1;
        } else if(arr[mid] < x) {
            lo = mid + 1;
        } else {
            //往左寻找
            int left = mid == 0 ? mid : mid - 1;
            for ( ;arr[left] == x; ) { left--; }

            //往右寻找
            int right = mid == arr.length - 1 ? mid : mid + 1;
            for ( ;arr[right] == x; ) { right++; }
            return right - left - 1;
        }
        return findXDupCount(arr, x, lo, hi);
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,3,3,3,4,5};
        FindXDupCount findXDupCount = new FindXDupCount();
//        System.out.println(findXDupCount.findXDupCount(nums, 3, 0, nums.length - 1));
        System.out.println(findXDupCount.findLastX(nums, 3, 0, nums.length - 1) -
            findXDupCount.findFirstX(nums, 3, 0, nums.length - 1) + 1);

    }

}
